Shortest Path First Algorithm (SPF)
Published: 2022-02-06
Also known as Dijkstra's algorithm. I have been working with OSPF and IS-IS for a long time but never actually read any explanation of how the SPF algorithm actually gets the job done. This post will therefore try to shed some light on what goes on behind the scenes when a router runs the SPF algorithm. The purpose is to build a shortest-path tree with our local R1 router as root, finding the shortest loop-free path to any destination in the network.
Network Topology
We will be using the topology below, focusing on the SPF calculations performed on R1. The linknet format is 10.X.Y.Z/29:
- X = Lower node ID
- Y = Higher node ID
- Z = Local node ID
For example, R3 IP-address on the R2-R3 link is 10.2.3.3/29.
SPF Algorithm in a nutshell
The calculations on each router is performed using two lists:
-
PATH list
This is the list of shortest paths for each destination. This table is sent to the routing table. Every entry in the list consist of three fields and values: Node ID, Metric, Next-hop.
-
TENT list
Short for tentative. A list of paths to each destination. The best one is picked and moved to the PATH list, others are discarded. Every entry in the list consist of three fields and values: Node ID, Metric, Next-hop.
We will assume all OSPF LSAs or IS-IS LSPs have been exchanged, R1 has received all link-state entries in the LSDB. The router refers to itself as the root node while running the algorithm. The algorithm then run the same steps in multiple iterations:
- Add a node to the PATH list and make it the path node. In the first iteration this is the local router.
- Add every path node neighbor to the TENT list. If the neighbor already exist in the TENT list but with a higher metric, replace the existing entry.
- ID is path node Router-ID
- Metric is root->path node metric + path->tent node metric
- Next-hop is path node interface address
- When all path node neighbors are in the TENT list, add the neighbor with lowest metric to the PATH list and remove it from the TENT list.
Repeat steps 1-3 until the TENT list is empty.
First iteration
In step 1, R1 makes itself the path-node. Step 2 adds R1s local neighbors R2 and R3 to the TENT list. In step 3, R2 is moved to the PATH list thanks to its lower metric and is also selected as the new Path Node.
R2 was selected because it is guaranteed to be the shortest path between R1 and R2. The higher metric to R3 makes it impossible for the R1-R3-R2 path to have a lower metric than the R1-R2 path.
Step 1:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | +-----------------------------+
+-----------------------------+
Step 2:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 2.2.2.2 | 2 | 10.1.2.2 |
+-----------------------------+ | 3.3.3.3 | 5 | 10.1.3.3 |
+-----------------------------+
Step 3:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 3.3.3.3 | 5 | 10.1.3.3 |
| 2.2.2.2 | 2 | 10.1.2.2 | +-----------------------------+
+-----------------------------+
Second iteration
We now process R2 and add its neighbors R3 and R4 to the TENT-list. The existing R3 TENT entry is replaced because the 2+2 metric via R2 is lower than the existing 5-metric entry. The R4 entry was also added.
In the third step, the R3 entry has the lowest metric in the TENT list and so is moved to the PATH list and selected as the next path-node.
Step 1:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 3.3.3.3 | 5 | 10.1.3.3 |
| 2.2.2.2 | 2 | 10.1.2.2 | +-----------------------------+
+-----------------------------+
Step 2:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 3.3.3.3 | 4 | 10.1.2.2 |
| 2.2.2.2 | 2 | 10.1.2.2 | | 4.4.4.4 | 9 | 10.1.2.2 |
+-----------------------------+ +-----------------------------+
Step 3:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 4.4.4.4 | 9 | 10.1.2.2 |
| 2.2.2.2 | 2 | 10.1.2.2 | +-----------------------------+
| 3.3.3.3 | 4 | 10.1.2.2 |
+-----------------------------+
Third iteration
R3 is processed, it has no new neighbors but it has a lower metric to R4 so the TENT list is updated with the better entry. Step 3 moves the remaining R4 entry in the TENT list to the PATH list and R4 is the new path-node.
Step 1:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 4.4.4.4 | 9 | 10.1.2.2 |
| 2.2.2.2 | 2 | 10.1.2.2 | +-----------------------------+
| 3.3.3.3 | 4 | 10.1.2.2 |
+-----------------------------+
Step 2:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | | 4.4.4.4 | 7 | 10.1.2.2 |
| 2.2.2.2 | 2 | 10.1.2.2 | +-----------------------------+
| 3.3.3.3 | 4 | 10.1.2.2 |
+-----------------------------+
Step 3:
+-----------------------------+ +-----------------------------+
| PATH list | | TENT list |
+-----------------------------+ +-----------------------------+
| ID | Metric | Next-hop | | ID | Metric | Next-hop |
+-----------------------------+ +-----------------------------+
| 1.1.1.1 | 0 | self | +-----------------------------+
| 2.2.2.2 | 2 | 10.1.2.2 |
| 3.3.3.3 | 4 | 10.1.2.2 |
| 4.4.4.4 | 7 | 10.1.2.2 |
+-----------------------------+
Fourth iteration
R4 is the path-node, but since it has no new neighbors the TENT list remains empty and the SPF calculation ends.
Final Shortest-Path Tree
The below topology is the result of the SPF calculation performed on R1 creating the shortest-path tree. This topology tree will remain until a LSA/LSP is received or withdrawn, triggering a new SPF calculation on R1.
